﻿#include <queue>
#include <algorithm>
#include <sstream> 
#include <iomanip>

using namespace msl;

// ====================
// Set Iterator
// ====================

template <typename T>
T* Set<T>::SetIterator::getptrSetElement() const {
    return &(p->els[el_ind]);
}

template <typename T>
Set<T>::SetIterator::SetIterator(Set<T>* par, int ind) : p(par), el_ind(ind) {
    // empty
}

template <typename T>
T& Set<T>::SetIterator::operator*() const {
    return p->els[el_ind];
}

template <typename T>
T* Set<T>::SetIterator::operator->() {
    return &(p->els[el_ind]);
}

template <typename T>
typename Set<T>::SetIterator& Set<T>::SetIterator::operator++() {
    if (!p->exist(2 * el_ind + 2)) {
        while (el_ind % 2 == 0 && el_ind != 0) el_ind = el_ind / 2 - 1;
        if (el_ind == 0) { el_ind = -1; return *this; }
        el_ind = el_ind / 2; return *this;
    }
    el_ind = 2 * el_ind + 2;
    while (p->exist(2 * el_ind + 1)) el_ind = 2 * el_ind + 1;

    return *this;
}

template <typename T>
typename Set<T>::SetIterator Set<T>::SetIterator::operator++(int) {
    typename Set<T>::SetIterator old_it = *this;
    ++(*this);
    return old_it;
}

template <typename T>
typename Set<T>::SetIterator& Set<T>::SetIterator::operator--() {
    if (el_ind == -1) {
        el_ind = 0;
        while (p->exist(2 * el_ind + 2)) el_ind = 2 * el_ind + 2;
        return *this;
    }

    if (!p->exist(2 * el_ind + 1)) {
        while (el_ind % 2 == 1 && el_ind != 0) el_ind = el_ind / 2;
        if (el_ind == 0) { el_ind = -1; return *this; }
        el_ind = el_ind / 2 - 1; return *this;
    }
    el_ind = 2 * el_ind + 1;
    while (p->exist(2 * el_ind + 2)) el_ind = 2 * el_ind + 2;

    return *this;
}

template <typename T>
typename Set<T>::SetIterator Set<T>::SetIterator::operator--(int) {
    typename Set<T>::SetIterator old_it = *this;
    --(*this);
    return old_it;
}

template <typename T>
bool Set<T>::SetIterator::operator==(const SetIterator& other) {
    return (this->el_ind == other.el_ind && this->p == other.p);
}

template <typename T>
bool Set<T>::SetIterator::operator!=(const SetIterator& other) {
    return !(*this == other);
}

// ====================
// Set Iterator
// ====================


template <typename T>
Set<T>::Set() : els(), used() {
    // empty
}

template <typename T>
Set<T>::Set(const Set& other) {
    copy(other);
}

template <typename T>
Set<T>::Set(std::initializer_list<T> values) {
    create_balance_tree(values);
}

template <typename T>
void Set<T>::create_balance_tree(std::vector<T> vals) {
    els = vector<T>();
    used = vector<bool>();
    sort(vals.begin(), vals.end());
    queue<pair<int, int> > q; q.push({ 0, vals.size() - 1 });
    while (!q.empty()) {
        pair<int, int> el = q.front(); q.pop();
        // cout << "ELS: " << el.first << " " << el.second << "\n";
        int l = el.first, r = el.second;
        if (l > r) continue;
        int m;
        if (l == r) m = l;
        else if (r < vals.size() / 2) m = (l + r + (l + r) % 2) / 2;
        else m = (l + r) / 2;
        insert(vals[m]);
        q.push({ l, m - 1 }); q.push({ m + 1, r });
    }
}

template <typename T>
Set<T>::~Set() {
    // empty (vector's destructors call automatically)
}

template <typename T>
void Set<T>::copy(const Set& other) {
    this->els = other.els;
    this->used = other.used;
}

template <typename T>
Set<T> Set<T>::operator=(const Set& other) {
    copy(other);
    return *this;
}

template <typename T>
bool Set<T>::exist(int ind) {
    return used.size() >= ind + 1 && used[ind];
}

template <typename T>
typename Set<T>::SetIterator Set<T>::begin() {
    int ind = 0;
    while (exist(2 * ind + 1)) ind = 2 * ind + 1;
    return SetIterator(this, ind);
}

template <typename T>
typename Set<T>::SetIterator Set<T>::end() {
    return SetIterator(this, -1);
}

template <typename T>
bool Set<T>::empty() const {
    return !exist(0);
}

template <typename T>
void Set<T>::clear() {
    els = vector<T>(0);
    used = vector<T>(0);
}

template <typename T>
typename Set<T>::SetIterator Set<T>::insert(T value) {
    int ind = 0;
    while (exist(ind)) {
        if (value < els[ind]) ind = 2 * ind + 1;
        else if (value == els[ind]) return SetIterator(this, ind);
        else ind = 2 * ind + 2;
    }

    els.resize(max((int)els.size(), ind + 1));
    used.resize(max((int)used.size(), ind + 1));
    els[ind] = value;
    used[ind] = 1;
    return SetIterator(this, ind);
}

template <typename T>
void Set<T>::erase(Set<T>::SetIterator it) {
    used[it.el_ind] = 0;
}

// ====================
// Functions for set 
// ====================

struct qset_element {
    int ind;
    int i;
    int j;
};

template <typename T>
string msl::print_set(Set<T>& s) {
    vector<vector<string> > tree;
    string res;

    queue<qset_element> q;
    if (s.exist(0)) {
        tree.resize(1);
        tree[0].resize(1);
        tree[0][0] = to_string(s.els[0]);
        q.push({ 0, 0, 0 });
    }
    while (!q.empty()) {
        auto el = q.front(); q.pop();
        // cout << s.els[el.ind] << " " << el.ind << " " << el.i << " " << el.j << endl;

        int ind = el.ind, lind = 2 * el.ind + 1, rind = 2 * el.ind + 2;
        if (s.exist(lind)) {
            tree[el.i].resize(max((int)tree[el.i].size(), el.j + 2));
            tree[el.i][el.j + 1] = to_string(s.els[lind]);
            q.push({ lind, el.i, el.j + 1 });
        }
        if (s.exist(rind)) {
            tree.resize(max((int)tree.size(), el.i + 2));
            tree[el.i + 1].resize(max((int)tree[el.i].size(), el.j + 2));
            tree[el.i + 1][el.j + 1] = to_string(s.els[rind]);
            q.push({ rind, el.i + 1, el.j + 1 });
        }
    }

    ostringstream oss;

    for (int i = 0; i < tree.size(); i++) {
        bool f = 1;
        for (int j = 0; j < tree[i].size(); j++) {
            if (f && tree[i][j].size() != 0) {
                f = 0;
                if (i != 0) oss << char(32) << char(192) << char(196); // " └─"
            }
            if (f && j == 0) { oss << setw(7) << ""; continue; }
            if (f && j != 0) { oss << setw(7 + 3) << ""; continue; }
            if (tree[i].size() > j + 1 && tree.size() >= i + 2 && tree[i + 1].size() >= j + 2)
                oss << setw(7) << tree[i][j] << char(196) << char(194) << char(196); // "─┬─"
            else if (tree[i].size() > j + 1)
                oss << setw(7) << tree[i][j] << char(196) << char(196) << char(196); // "───"
            else if (!(tree[i].size() > j + 1) && tree.size() >= i + 2 && tree[i + 1].size() >= j + 2)
                oss << setw(7) << tree[i][j] << char(196) << char(191) << char(32); // "─┐ "
            else
                oss << setw(7) << tree[i][j];
        }
        oss << "\n";
    }

    res = oss.str();
    return res;
}

template <typename T>
int msl::leaf_count(Set<T>& s) {
    int res = 0;
    for (auto it = s.begin(); it != s.end(); it++) {
        if (!s.exist(2 * it.el_ind) && !s.exist(2 * it.el_ind + 1)) res++;
    }
    return res;
}

